翻訳と辞書
Words near each other
・ Kraft Foods Banbury
・ Kraft Foods Inc
・ Kraft Heinz
・ Kraft Hockeyville
・ Kraft Mayo
・ Kraft Music Hall
・ Kraft Music Hall (TV series)
・ Kraft paper
・ Kraft process
・ Kraft Schepke
・ Kraft Singles
・ Kraft Super Fli
・ Kraft Suspense Theatre
・ Kraft Television Theatre
・ Kraft VI, Count of Hohenlohe-Weikersheim
Kraft's inequality
・ Kraft, Louisiana
・ Kraft, Prince of Hohenlohe-Langenburg
・ Kraftisried
・ Kraftklub
・ Kraftprobe
・ Kraftsdorf
・ Kraftverkene i Øvre Namsen
・ Kraftwerk
・ Kraftwerk (album)
・ Kraftwerk 2
・ Kraftwerk discography
・ Kraftwerke Oberhasli
・ KraftWorks
・ Krafty


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Kraft's inequality : ウィキペディア英語版
Kraft's inequality
In coding theory, Kraft's inequality, named after Leon Kraft, gives both a necessary and sufficient condition for the existence of a prefix code〔 for a given set of codeword lengths. Its applications to prefix codes and trees often find use in computer science and information theory.
More specifically, Kraft's inequality limits the lengths of codewords in a prefix code: if one takes an exponential of the length of each valid codeword, the resulting set of values must look like a probability mass function, that is, it must have total measure less than or equal to one. Kraft's inequality can be thought of in terms of a constrained budget to be spent on codewords, with shorter codewords being more expensive.
* If Kraft's inequality holds with strict inequality, the code has some redundancy.
* If Kraft's inequality holds with equality, the code in question is a complete code.
* If Kraft's inequality does not hold, the code is not uniquely decodable.
Kraft's inequality was published by . However, Kraft's paper discusses only prefix codes, and attributes the analysis leading to the inequality to Raymond Redheffer. The inequality is sometimes also called the Kraft–McMillan theorem after the independent discovery of the result by ; McMillan proves the result for the general case of uniquely decodable codes, and attributes the version for prefix codes to a spoken observation in 1955 by Joseph Leo Doob.
== Examples ==


抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Kraft's inequality」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.